package Alibaba;

import java.util.*;

/**
 * @author zhangmin
 * @create 2022-01-20 19:50
 *
 * 140. 单词拆分 II
 * 给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，在字符串中增加空格来构建一个句子，
 * 使得句子中所有的单词都在词典中。返回所有这些可能的句子。
 * 思路：回溯：使用哈希表存储字符串 s 的每个下标和从该下标开始的部分可以组成的句子列表
 * 路径：已组成句子的部分
 * 选择列表：部分是wordDict中的一个单词
 * 终止条件：整个s构成句子
 */
public class wordBreak140 {

    LinkedList<LinkedList<String>> backtrack(String s, HashSet<String> wordset, int index, Map<Integer,LinkedList<LinkedList<String>>> map){
        if (!map.containsKey(index)){
            LinkedList<LinkedList<String>> wordBreaks=new LinkedList<>();
            if (index==s.length()){
                wordBreaks.add(new LinkedList<>());
            }
            for (int i = index+1; i <= s.length(); i++) {
                String word = s.substring(index, i);
                if (wordset.contains(word)){
                    LinkedList<LinkedList<String>> lists = backtrack(s, wordset, i, map);
                    for (LinkedList<String> list:lists) {
                        LinkedList<String> wordlist=new LinkedList<>(list);
                        wordlist.offerFirst(word);
                        wordBreaks.add(wordlist);
                    }
                }
            }
            map.put(index,wordBreaks);
        }
        return map.get(index);
    }
    public List<String> wordBreak(String s, List<String> wordDict) {
        HashSet<String> set=new HashSet<>(wordDict);
        Map<Integer,LinkedList<LinkedList<String>>> map=new HashMap<>();
        LinkedList<LinkedList<String>> lists = backtrack(s, set, 0, map);
        List<String> res=new LinkedList<>();
        for (LinkedList<String> list:lists) {
            res.add(String.join(" ",list));
        }
        return res;
    }
}
